package DataStructure.linkList;

import utils.CommonUtils;

/**
 * 题目简述：反转链表，每三个节点进行一次反转。例如{1,2,3,4,5,6,7,8}转换为{3,2,1,6,5,4,8,7}
 */
public class ReverseList3 {

    public static void main(String[] args) {
        ListNode listNode = new ReverseList3().reverseList(CommonUtils.makeNodeList(new int[]{1,2,3,4,5,6,7,8}));
        System.out.println(listNode.val);
    }
    /**
     * 思路：递归函数：reverse(当前链表头结点head，子链表长度)
     * 递归函数体：使用双指针反转链表思路，反转head开始长度最多为3的子链表，最后pre指向的即为新子链表的头结点，cur指向的即为下一层链表头结点，
     * 将新子链表的尾结点即head的next指向对下一层进行递归的返回结果，最后返回当前新子链表的头结点。
     */
    public ListNode reverseList(ListNode head) {
        return reverse(head, 3);
    }
    public ListNode reverse(ListNode head, int length) {
        if (head == null) return null;
        ListNode newTail = head;//新子链表的尾结点即为当前头结点
        int count = 1;
        ListNode pre = null, cur = head;//使用双指针反转链表思路反转当前子链表
        while (count <= length && cur != null) {//当扫描的子链表长度超出length或者cur指向null时完成反转
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
            count++;
        }
        //将新子链表的尾结点指向下一层新子链表的头结点
        newTail.next = reverse(cur, length);//当前cur指向的即为下一层头结点，对下一层子链表进行反转
        return pre;//将新子链表的头结点返回
    }
}
